선형 계획법(Linear Programming)

객체를 변수의 선형 함수로 명시하고,

자원에 대한 제한성을 등식과 부등식으로 정의

- 최소화 선형 계획법

- 최대화 선형 계획법

- 정규형

: 선형 부등식을 조건으로 하는 선형 함수의 최대화

- 이완형

: 선형 등식을 조건으로 하는 선형 함수의 최대화

about Maximize x1+x2 $x_1+x_2$ Subject to 4x1−x2≤8 $4x_1-x_2\leq 8$ 2x1+x2≤10 $2x_1+x_2\leq 10$ 5x1−2x2≥−2 $5x_1-2x_2\geq -2$ x1,x2≥0 $x_1, x_2 \geq 0$

심플렉스 알고리즘(Simplex Algorithm)

볼록한 심플렉스(조건 만족 반-공간에 의해 형성 가능한 영역)가 정점에서 발생함을 이용해서

목적 함수의 최대값을 갖는 지점을 리턴

선형 계획법의 정규형으로의 변환

선형 계획법의 이완형으로의 변환

선형 계획법 문제의 조건들을 이완형으로 변환시, 심플렉스 알고리즘을 통해 효율적으로 해를 구할 수 있다.